import java.util.*;
public class Solution {
    public int countCollisions(String directions) {
        char[] s = directions.toCharArray();
        int i = 0;
        int j = s.length - 1;
        while(i < j && s[i] == 'L'){
            i++;
        }
        while(i < j && s[j] == 'R'){
            j--;
        }
        int cnt = 0;
        for(int k = i; k < j; k++){
            if(s[k] == 'S'){
                cnt++;
            }
        }
        return j - i + 1 - cnt;
    }

    public void moveZeroes(int[] nums) {
        int i = 0;
        int j = 0;
        for(i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j++;
            }
        }
    }

    private boolean check(int x, int y, char[][] grid){
        //检查合法性
        //可以走
        if(x >= 0 && x < grid.length
        && y >= 0 && y < grid[0].length
        && grid[x][y] == '1'){
            return true;
        }
        return false;
    }

    private void dfs(int x, int y, char[][] grid){
        grid[x][y] = 0;
        //上
        //如果可以走
        if(check(x - 1, y, grid)){
            dfs(x - 1, y, grid);
        }
        //下
        if(check(x + 1, y, grid)){
            dfs(x + 1, y, grid);
        }
        //左
        if(check(x, y - 1, grid)){
            dfs(x, y - 1, grid);
        }
        //右
        if(check(x, y + 1, grid)){
            dfs(x, y + 1, grid);
        }
    }

    public int numIslands(char[][] grid) {
        int ans = 0;

        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                //对每一个点进行深度优先遍历
                if(grid[i][j] == '1'){
                    ans++;
                    dfs(i, j, grid);
                }
            }
        }
        return ans;
    }

    public static int myBinarySearch(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;
        while(left <= right){
            System.out.println(left + " " + right);
            int mid = left + ((right - left) >> 1);
            if(arr[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,6};
        int target = 5;
        System.out.println(myBinarySearch(arr, target));
    }
}
